/**************************************************************************************************
* Title: SumHeapAllocator.h
* Author: Gael Huber
* Description: General purpose heap allocator
**************************************************************************************************/
#ifndef __SUMHEAPALLOCATOR_H__
#define __SUMHEAPALLOCATOR_H__

#include <malloc.h>
#include <assert.h>
#include "SumPointerTree.h"
#include "SumLengthTree.h"

class HeapAllocator {
public:
	// Constructor
	inline explicit HeapAllocator(size_t size)
		: pointerTree(0), lengthTree(0), blockStart(0), totalAllocated(size), minSize(32)
	{ 
		initialize();
	}

	// Destructor
	inline ~HeapAllocator(void) {
		free(blockStart);
	}

	void* const alloc(size_t bytes);	// Allocate a block of memory
	void free(void* address);		// Free a block of memory

	// Peek at the root memory address
	inline const MemAddress peek(void) const
	{
		return pointerTree->minimum(pointerTree->getRoot())->getAddress();
	}

private:
	void initialize(void);	// Initialize the heap allocator
	void splitBlock(size_t bytes, PointerTree::Node* pn, LengthTree::Node* ln);	// Split a block of memory of size bytes and the remainder
	void mergeBlocks(void* a, void* b);	// Merge two blocks at the corresponding addresses

	PointerTree* pointerTree;	// Tree representing pointers to all free blocks of memory
	LengthTree* lengthTree;		// Tree representing length of all free blocks of memory
	void* blockStart;			// Pointer to the start of the block
	size_t totalAllocated;		// Total allocated space
	const size_t minSize;	// Minimum number of bytes per allocation
};

// Overload new and delete for the benefit of the stack allocator

// Overload new for syntactic ease-of-use (permits regular initialization/allocation of objects)
static inline void* operator new (size_t size, HeapAllocator& ha)
{
	return ha.alloc(size);
}

// Overload new[] for syntactic ease-of-use (permits regular initialization/allocation of arrays)
static inline void* operator new[] (size_t size, HeapAllocator& ha)
{
	return ha.alloc(size);
}

// Overload delete for syntactic ease-of-use (permits regular deletion of objects)
static inline void operator delete (void* mem, HeapAllocator& ha)
{
	ha.free(mem);
}

// Overload delete[] for syntactic ease-of-use (permits regular deletion of array objects
static inline void operator delete[] (void* mem, HeapAllocator& ha)
{
	ha.free(mem);
}

#endif